package cxydmmszl.chapter09.t157;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;

/**
 * <li style="color: red;">Prob</li>
 * LFU 缓存结构设计
 * <li style="color: green;">Desc</li>
 * 一个缓存结构需要实现如下功能：<br/>
 * &emsp;&emsp;set(key, value)：将记录(key, value)插入该结构<br/>
 * &emsp;&emsp;get(key)：返回key对应的value值<br/>
 * 但是缓存结构中最多放 K 条记录，如果新的第 K+1 条记录要加入，
 * 就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：<br/>
 * 在缓存结构的 K 条记录中，哪个 key 从进入缓存结构的时刻开始，
 * 被调用 set 或者 get 的次数最少，就删掉这个 key 的记录；
 * 如果调用次数最少的 key 有多个，上次调用发生最早的 key 被删除。<br/>
 * 这就是 LFU 缓存替换算法。实现这个结构，K 作为参数给出。
 * <br/><br/>[要求]<br/>
 * set 和 get 方法的时间复杂度为 O(1)
 * <br/><br/>备注：<br/>
 * 1⩽K⩽N⩽10^5<br/>
 * −2∗10^9⩽x,y⩽2∗10^9
 * <li style="color: green;">Input</li>
 * 第一行两个个整数N, K，表示操作数量以及缓存结构大小<br/>
 * 接下来N行，第一行一个整数opt表示操作类型。<br/>
 * 若opt=1，接下来两个整数x, y，表示set(x, y)<br/>
 * 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
 * <li style="color: green;">Output</li>
 * 对于每个操作 2，输出一个答案
 * <li style="color: blue;">Link</li> CD65
 *
 * @author habitplus
 * @since 2021-11-01 10:41
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException("Input is invalid!");
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int k = nextInt();

        LFUCache<Integer, Integer> cache = new LFUCache<>(k);
        StringBuilder sb = new StringBuilder();
        int opt, x, y;
        while (n-- > 0) {
            opt = nextInt();
            if (opt == 1) {
                // set
                x = nextInt();
                y = nextInt();
                cache.set(x, y);
            } else {
                // get
                x = nextInt();
                Integer v = cache.get(x);
                sb.append(v == null ? -1 : v).append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}

/*
    定义双向链表的结点数据类型
 */
class Node<K, V> {
    K key;
    V val;
    Node<K, V> prev;
    Node<K, V> next;

    public Node(K key, V val) {
        this.key = key;
        this.val = val;
    }
}

/*
    定义双向桶链表结点的数据类型
 */
class BucketNode<K, V> {
    // 桶中有一个双向链表
    Node<K, V> head;
    Node<K, V> tail;
    // 当前桶的调用次数（get 和 set）
    int visitedCnt;
    BucketNode<K, V> prev;
    BucketNode<K, V> next;

    public BucketNode(Node<K, V> node, int visitedCnt) {
        this.head = node;
        this.tail = node;
        this.visitedCnt = visitedCnt;
    }

    /*
        把一个新的节点加入这个桶，新的节点都放在顶端变成新的头部
     */
    public void addNodeFromHead(Node<K, V> newHead) {
        if (newHead == null) return;
        newHead.next = head;
        head.prev = newHead;
        head = newHead;
    }

    /*
        删除 node 节点，并保证 node 的前后节点重新连接
     */
    public void deleteNode(Node<K, V> node) {
        if (head == tail) {
            // 只有一个节点
            head = null;
            tail = null;
        } else {
            if (node == head) {
                // 删除的是头结点
                head = node.next;
                head.prev = null;
            } else if (node == tail) {
                // 删除的是尾结点
                tail = node.prev;
                tail.next = null;
            } else {
                // 删除的是中间节点
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            // 将 node 节点独立出来
            node.prev = null;
            node.next = null;
        }
    }
}


class LFUCache<K, V> {
    // 表示 key 由哪个节点代表
    private HashMap<K, Node<K, V>> keyNodeMap;
    // 表示节点在哪个桶里面
    private HashMap<Node<K, V>, BucketNode<K, V>> nodeBucketMap;
    // 只记录 双向桶链表的第一个桶
    private BucketNode<K, V> bucketListHead;
//    private BucketNode<K, V> bucketListTail;
    private final int capacity;

    public LFUCache(int capacity) {
        if (capacity < 1) {
            throw new RuntimeException("The capacity must be more than 0 : " + capacity);
        }
        this.keyNodeMap = new HashMap<>();
        this.nodeBucketMap = new HashMap<>();
        this.bucketListHead = null;
//        this.bucketListTail = null;
        this.capacity = capacity;
    }

    public V get(K key) {
        if (!keyNodeMap.containsKey(key)) return null;
        Node<K, V> node = keyNodeMap.get(key);
        BucketNode<K, V> curBucket = nodeBucketMap.get(node);
        move(node, curBucket);
        return node.val;
    }

    public void set(K key, V value) {
        if (keyNodeMap.containsKey(key)) {
            // 存在 key，修改节点的 val，移除当前所在桶，并插入下一个桶的尾部
            Node<K, V> node = keyNodeMap.get(key);
            node.val = value;
            BucketNode<K, V> curBucket = nodeBucketMap.get(node);
            move(node, curBucket);
        } else {
            if (keyNodeMap.size() == capacity) {
                // 已达到缓存容量的上限，需要第一个桶的最后一个节点
                Node<K, V> rNode = bucketListHead.tail;
                bucketListHead.deleteNode(rNode);
                modifyBucketList(bucketListHead);
                keyNodeMap.remove(rNode.key);
                nodeBucketMap.remove(rNode);
            }
            // 新建结点，该节点应该是要放在次数为 1 的桶里
            // 而且该节点必然是放在第一个桶内，或者第一个桶的前一个桶内（新建）
            Node<K, V> newNode = new Node<>(key, value);
            if (bucketListHead == null) {
                // 没有桶
                bucketListHead = new BucketNode<>(newNode, 1);
            } else {
                if (bucketListHead.visitedCnt == 1) {
                    // 放第一个桶内
                    bucketListHead.addNodeFromHead(newNode);
                } else {
                    // 新建一个访问次数为 1 的桶，并放入 newNode
                    BucketNode<K, V> newBucket = new BucketNode<>(newNode, 1);
                    newBucket.next = bucketListHead;
                    bucketListHead.prev = newBucket;
                    bucketListHead = newBucket;
                }
            }

            keyNodeMap.put(key, newNode);
            nodeBucketMap.put(newNode, bucketListHead);
        }
    }

    /*
        将 node 从 oldBucket 中移出，并放入【次数+1】的下一个桶中（尾部）
        整个过程既要保证桶之间的双向链表，也要保证节点之间的双向链表
     */
    private void move(Node<K, V> node, BucketNode<K, V> oldBucket) {
        oldBucket.deleteNode(node);
        // preBucket 表示【次数+1】的前一个桶
        // 如果 oldBucket 在移出 node 后还有节点，那 oldBucket 就是【次数+1】的桶的前一个桶
        // 否则，oldBucket 是需要删除的，因此【次数+1】的桶的前一个桶就是 oldBucket 的前一个桶
        BucketNode<K, V> preBucket = modifyBucketList(oldBucket) ? oldBucket.prev : oldBucket;
        // nextBucket 表示【次数+1】的后一个桶
        BucketNode<K, V> nxtBucket = oldBucket.next;

        if (nxtBucket == null) {
            // 后一个桶为空
            // 新建【次数+1】的桶
            BucketNode<K, V> newBucket = new BucketNode<>(node, oldBucket.visitedCnt + 1);
            if (preBucket != null) {
                preBucket.next = newBucket;
            }
            newBucket.prev = preBucket;
            if (bucketListHead == null) {
                bucketListHead = newBucket;
            }
            nodeBucketMap.put(node, newBucket);
        } else {
            if (nxtBucket.visitedCnt == oldBucket.visitedCnt + 1) {
                // 【次数+1】的桶正好是 nxtBucket，直接将该节点加入到 nxtBucket 中的双向链表的头结点
                nxtBucket.addNodeFromHead(node);
                nodeBucketMap.put(node, nxtBucket);
            } else {
                // 【次数+1】的桶应该位于 nxtBucket 的前一个桶
                BucketNode<K, V> newBucket = new BucketNode<>(node, oldBucket.visitedCnt + 1);
                if (preBucket != null) preBucket.next = newBucket;
                newBucket.prev = preBucket;
                newBucket.next = nxtBucket;
                nxtBucket.prev = newBucket;
                if (bucketListHead == nxtBucket) {
                    bucketListHead = newBucket;
                }
                nodeBucketMap.put(node, newBucket);
            }
        }
    }

    /*
        curBucket 为刚刚减少了一个节点的桶，现在需要判断该桶是否需要删除，
        1. 要删除，返回 true
        2. 不要删除，返回 false;
     */
    private boolean modifyBucketList(BucketNode<K, V> curBucket) {
        if (curBucket.head != null) return false;
        if (bucketListHead == curBucket) {
            // 要删除的桶是第一个桶
            bucketListHead = curBucket.next;
            if (bucketListHead != null) bucketListHead.prev = null;
        } else {
            curBucket.prev.next = curBucket.next;
            if (curBucket.next != null) curBucket.next.prev = curBucket.prev;
        }
//        curBucket.prev = null;
//        curBucket.next = null;
        return true;
    }
}
